/**
 * FileName: Exercise1435.c
 * ------------------------------------------------------------------------------------------------------------
 * 14.28 Write a program that inserts $N/2$ random integers into a table of size $N$ using linear probing,
 * then computes the average cost of a search miss in the resulting table from the cluster lengths,
 * for $N=10^{3}$, $10^{4}$, $10^{5}$, and $10^{6}$.
 *
 * 14.35 Modify your solution to Exercise 14.28 to use double hashing.
 * ------------------------------------------------------------------------------------------------------------
 * Property 14.3 When collisions are resolved with linear probing, the average number of probes required to search
 * in a hash table of size $M$ that contains $N = \alpha M$ keys is about
    $$
    \frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)
    $$
    for misses.
 * ----------------------------------------------------------------------------------------------
 * Property 14.4 When collisions are resolved with double hashing, the average number of probes required to search in a hash table of size $M$ that contains $N = \alpha M$ keys is about
    $$
    \frac{1}{(1 - \alpha)^2}
    $$
 * for misses.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Item相关
typedef int Key;
typedef int Value;
typedef struct Item* Item;

struct Item {
    Key key;
    Value value;
};

// 注意：这些宏的参数是 Item* 类型，因此比较的是其内部的 key 成员
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL
#define null(A) (st[A] == NULLitem || st[A] == DELETED_ITEM_SENTINEL)

#define hashtwo(v) ((v % 97)+1)

static int N; //表中键的数量
static int M; //表中槽位的数量
static Item *st;
static Item DELETED_ITEM_SENTINEL;

//hash函数声明
int hash(int);
Item createItem(Key, Value);
//符号表操作声明
void STinit(int);
int STcount();
void STinsert(Item);
Item STsearch(Key);
void STDelete(Item);

//hash函数实现
int hash(int x) {
    return (11 * x) % M;
}
/**
 * @brief 分析线性探测哈希表中的簇信息。
 * 计算簇的总数量，并打印每个簇的起始索引和长度。
 *
 * @param table_size 哈希表的总槽位数量 M。
 * @param hash_table 指向哈希表数组的指针 st。
 * @param is_null_func 用于判断槽位是否为空的函数指针。
 * 这里简化为直接使用全局的 st 和 null 宏。
 * @return int 簇的总数量。
 */
int analyze_clusters(int table_size, Item *hash_table) {
    int cluster_count = 0;
    // printf("\n--- Cluster Analysis (M=%d) ---\n", table_size);

    int i = 0;
    int sum = 0;
    while (i < table_size) {
        // 查找簇的起点
        // 条件1: 当前槽位是非空的
        // 条件2: 这是表的第一个槽位，或者前一个槽位是空的
        if (!null(i) && (i == 0 || null(i - 1))) {
            cluster_count++;
            int cluster_start_index = i;
            int current_cluster_length = 0;

            // 计算当前簇的长度
            int j = i;
            while (j < table_size && !null(j)) {
                current_cluster_length++;
                j++;
            }
            // printf("  Cluster %d: starts at index %d, length %d\n",
            //        cluster_count, cluster_start_index, current_cluster_length);

            sum += current_cluster_length * current_cluster_length;

            // 跳过已处理的簇，从下一个可能的新簇起点开始
            i = j;
        } else {
            i++; // 移动到下一个槽位
        }
    }
    double average_cost = 1 + (double)N/(2*M) + (double)sum/(2*M);
    double alpha = (double)N/M;
    double theory_cost = 1/(1-alpha);

    // printf("--- End Cluster Analysis ---\n");
    // printf("Total number of clusters: %d\n", cluster_count);

    printf("Double hashing symbol table(M=%d):the average cost of unsuccessful search in that table is %f, theory cost: %f\n", table_size,
        average_cost, theory_cost);
    return cluster_count;
}

// 符号表操作实现
void STinit(int max) {
    int i;
    N = 0;
    M = 2 * max;
    st = malloc(M * sizeof(Item));
    DELETED_ITEM_SENTINEL = createItem(-1, -1);
    for (i = 0; i < M; i++) {
        st[i] = NULLitem;
    }
}

int STcount() {
    return N;
}

void STinsert(Item item) {
    Key v = key(item);
    int i = hash(v);
    int k = hashtwo(v);
    while (!null(i)) {
        i = (i+k)%M;
    }
    st[i] = item;
    N++;
}

Item STsearch(Key v) {
    int i = hash(v);
    int k = hashtwo(v);
    while (!null(i)) {
        if (eq(v, key(st[i]))) {
            return st[i];
        }else {
            i = (i+k)%M;
        }
    }
    return NULLitem;
}

void STDelete(Item item) {
    Key v = key(item);
    int i = hash(v);
    int k = hashtwo(v);
    while (!null(i)) {
        if (eq(v, key(st[i]))) {
            free(st[i]);
            st[i] = DELETED_ITEM_SENTINEL;
            N--;
            return;
        }else {
            i = (i+k)%M;
        }
    }
}

//测试函数声明
void test_insert_1000();
void test_insert_10000();
void test_insert_100000();
void test_insert_1000000();
Item createItem(Key, Value);

int main(int argc, char* argv[]) {
    srand(time(NULL));
    // test_insert_1000();
    // test_insert_10000();
    // test_insert_100000();
    test_insert_1000000();
    return 0;
}

/**
 * createItem 函数：创建一个新的 Item 实例
 * @param k 键值
 * @param v 数值
 * @return 指向新创建 Item 的指针
 */
Item createItem(Key k, Value v) {
    Item newItem = malloc(sizeof(*newItem));
    newItem->key = k;
    newItem->value = v;
    return newItem;
}

//测试函数实现
void test_insert_1000() {
    STinit(500);

    int i;
    float alpha = (float)1/2;
    // float alpha = (float)2/3;
    // float alpha = (float)3/4;
    // float alpha = (float)9/10;
    for (i = 0; i < M*alpha; i++) {
        Key v = rand()%M;
        STinsert(createItem(v, v));
    }

    // 调用簇分析函数
    analyze_clusters(M, st);

}

void test_insert_10000() {
    STinit(5000);

    int i;
    float alpha = (float)1/2;
    // float alpha = (float)2/3;
    // float alpha = (float)3/4;
    // float alpha = (float)9/10;
    for (i = 0; i < M*alpha; i++) {
        Key v = rand()%M;
        STinsert(createItem(v, v));
    }

    // 调用簇分析函数
    analyze_clusters(M, st);

}

void test_insert_100000() {
    STinit(50000);

    int i;
    float alpha = (float)1/2;
    // float alpha = (float)2/3;
    // float alpha = (float)3/4;
    // float alpha = (float)9/10;
    for (i = 0; i < M*alpha; i++) {
        Key v = rand()%M;
        STinsert(createItem(v, v));
    }

    // 调用簇分析函数
    analyze_clusters(M, st);

}

void test_insert_1000000() {
    STinit(500000);

    int i;
    // float alpha = (float)1/2;
    // float alpha = (float)2/3;
    float alpha = (float)3/4;
    // float alpha = (float)9/10;
    for (i = 0; i < M*alpha; i++) {
        Key v = rand()%M;
        STinsert(createItem(v, v));
    }

    // 调用簇分析函数
    analyze_clusters(M, st);

}